package leetcode_100;

/**
 *@author 周杨
 *SearchA2DMatrix_74 在一个有序的二维数组中搜索一个数
 *describe: 用二分查找的思想 分治查找 AC 95%
 *2018年5月13日 上午9:56:34
 */
public class SearchA2DMatrix_74 {
	int[][] matrix;
	int target;
	int row;
	int col;
	public static void main(String[] args) {
		SearchA2DMatrix_74 test=new SearchA2DMatrix_74();
		int[][] matrix=new int[][] {{1,3,5,7},{10,11,16,20},{23,30,34,50}};
		int [][] matrix1=new int[][] {{1},{3}};
		System.out.println(test.searchMatrix(matrix1, 0));

	}
	
	public boolean searchMatrix(int[][] matrix, int target) {
	        this.matrix=matrix;
	        this.target=target;
	        this.row=matrix.length-1;
	        if(row==-1)
	        	return false;
	        this.col=matrix[0].length-1;
	        if(col==-1)
	        	return false;
	        return help(0,row,0,col);
	}

	private boolean help(int row1, int row2, int col1, int col2) {
		if(row1>row2||col1>col2)
			return false;
		if(row1==row2) {//被搜数可能就在此行
			if(this.target>matrix[row1][col2]||this.target<matrix[row1][col1])
				return false;
			else {
				if(col1==col2) {
					if(this.matrix[row1][col1]==this.target)
						return true;
					return false;
				}
				int evenCol=(col1+col2)/2;
				if(this.target>matrix[row1][evenCol])
					return help(row1,row2,evenCol+1,col2);
				else if(this.target<matrix[row1][evenCol])
					return help(row1,row2,col1,evenCol-1);
				else
					return true;
			}
		}
		else {//被搜数不在此行
			int evenRow=(row1+row2)/2;
			if(this.matrix[evenRow][col1]>this.target) {
				return help(row1,evenRow-1,col1,col2);
			}
			else if(this.matrix[evenRow][col2]<this.target)
				return help(evenRow+1,row2,col1,col2);
			else
				return help(evenRow,evenRow,col1,col2);
		}
	}
}
